#
# @lc app=leetcode.cn id=1541 lang=python3
#
# [1541] 平衡括号字符串的最少插入次数
#

# @lc code=start
class Solution:
    def minInsertions(self, s: str) -> int:
        insert_cnt, left_cnt, idx = 0, 0, 0

        while idx < len(s):
            # 左括号
            match s[idx]:
                case '(':
                    left_cnt += 1
                    idx += 1
            # 右括号
                case ')':
                    # 无左括号匹配
                    if left_cnt > 0:
                        left_cnt -= 1
                    else:
                        insert_cnt += 1
                    # )不够2个
                    if idx+1 < len(s) and s[idx+1] == ')':
                        idx += 2
                    else:
                        insert_cnt += 1
                        idx += 1
        insert_cnt += left_cnt*2
        return insert_cnt

# @lc code=end

